1. Field of the Invention
This invention relates in general to the field of instruction execution in computers, and more particularly to an apparatus and method for predicting the outcome of branch instructions in a pipeline microprocessor.
2. Description of the Related Art
An application program for execution on a microprocessor consists of a structured series of macro instructions that are stored in sequential locations in memory. A current instruction pointer within the microprocessor points to the address of the instruction currently being executed and a next instruction pointer within the microprocessor points to the address of the next instruction for execution. During each clock cycle, the length of the current instruction is added to the contents of the current instruction pointer to form a pointer to a next sequential instruction in memory. The pointer to the next sequential instruction is provided to logic that updates the next instruction pointer. If the logic determines that the next sequential instruction is indeed required for execution, then the next instruction pointer is updated with the pointer to the next sequential instruction in memory. Thus, macro instructions are fetched from memory in sequence for execution by the microprocessor.
Obviously, because a microprocessor is designed to execute instructions from memory in the sequence that they are stored, it follows that a program configured to execute macro instructions sequentially from memory is one which will run efficiently on the microprocessor. For this reason, most application programs are designed to minimize the number of instances where macro instructions are executed out of sequence. These out-of-sequence instances are known as jumps, or branches.
A program branch presents a problem because most conventional microprocessors do not simply execute one instruction at a time. Rather, a present day microprocessor consists of a number of pipeline stages, each stage performing a specific function. Instructions, inputs, and results from one stage to the next are passed in synchronization with a pipeline clock. Hence, several instructions may be executing in different stages of the microprocessor pipeline within the same clock cycle. As a result, when logic within a given stage determines that a program branch is to occur, then previous stages of the pipeline, that is, stages that are executing instructions following in sequence, must be cast out to begin execution of sequential macro instructions beginning with the instruction directed by the branch, or the branch target instruction. This casting out of previous pipeline stages is known as flushing and refilling the pipeline.
A conditional branch is a branch that may or may not occur, depending upon an evaluation of some specified condition. And, this evaluation is typically performed in later stages of the microprocessor pipeline. To preclude wasting many clock cycles associated with flushing and refilling the pipeline, present day microprocessors also provide logic in an early pipeline stage that predicts whether a conditional branch will occur or not. If it is predicted that a conditional branch will occur, then only those instructions prior to the early pipeline stage must be flushed, including those in the instruction buffer. Even so, this is a drastic improvement; correctly predicted branches are executed in roughly two clock cycles. But an incorrect prediction takes many more cycles to execute than if no branch prediction mechanism had been provided in the first place. The accuracy of branch predictions in a pipeline processor therefore significantly impacts the processor""s performance, for better or worse.
Yet, present day branch prediction techniques chiefly predict the outcome of a given conditional branch instruction in an application program based upon outcomes obtained when the conditional branch instruction was previously executed within the same instance of the application program. Historical branch prediction, or dynamic branch prediction, is effective because conditional branch instructions tend to exhibit repetitive outcome patterns when executed within an application program.
The historical outcome data is stored in a branch history table that is accessed using the address of a conditional branch instruction-a unique identifier for the instruction. A corresponding entry in the branch history table contains the historical outcome data associated with the conditional branch instruction. A dynamic prediction of the outcome of the conditional branch instruction is made based upon the contents of the corresponding entry in the branch history table.
Yet, because most present day microprocessors have address ranges on the order of gigabytes, it is not practical for a branch history table to be as large as the microprocessor""s address range. Because of this, smaller branch history tables are provided, on the order of kilobytes, and only low order bits of a conditional branch instruction""s address are used as an index into the table. But this presents another problem: because low order address bits are used to index the branch history table, two or more conditional branch instructions can index the same entry. This is known as aliasing. As such, the outcome of a more recently executed conditional branch instruction will replace the outcome of a formerly executed conditional branch instruction that is aliased to the same table entry. If the former conditional branch instruction is encountered again, its historical outcome information is unavailable to be used for a dynamic prediction.
Because dynamic predictions are sometimes not available, an alternative prediction is made for the outcome of a conditional branch instruction, usually based solely upon some static attribute of the instruction, such as the relative direction of a branch target instruction as compared to the address of the conditional branch instruction. This alternative prediction is called a static prediction because it is not based upon a changing execution environment within an application program. The static branch prediction is most often used as a fallback in lieu of a dynamic prediction. Hence, when a dynamic prediction is unavailable, the static prediction is used.
The present inventors have observed that the outcomes of some conditional branch instructions, when observed on pipeline microprocessor executing today""s predominant desktop computer application programs, exhibit a bias toward one outcome or the other, totally as a function of static indicators such as the type of conditional test performed, regardless of historical outcome data associated with the instructions. These instructions are called biased outcome conditional branch instructions. And, it has also been observed that the entries in a branch history table associated with other conditional branch instructions that exhibit no such bias, are at times negatively impacted as a result of updates occurring from biased outcome instructions which are aliased to the same entries.
Thus, the accuracy of branch predictions is degraded on the whole in a microprocessor that allows the outcomes of biased conditional branch instructions to impact the historical outcome data for conditional branch instructions that do not exhibit a static bias.
Therefore, what is needed is an apparatus for predicting the outcomes of branch instructions that is more accurate than has heretofore been provided.
In addition, what is needed is a branch prediction mechanism in a microprocessor that favorably utilizes static indicators of a conditional branch instruction to predict its outcome.
Furthermore, what is needed is an apparatus in a microprocessor for predicting branches that eliminates the effects of outcomes of biased outcome conditional branch instructions on data regarding historical outcomes for unbiased outcome conditional branch instructions.
Moreover, what is needed is a method in a microprocessor for mandating that the microprocessor use a static branch prediction over a dynamic prediction and for precluding the outcome of a conditional branch instruction whose static prediction was mandated from influencing outcome data in a branch history table.
To address the above-detailed deficiencies, it is an object of the present invention to provide a static branch prediction apparatus that provides accurate branch predictions for biased outcome conditional branch instructions and unbiased outcome conditional branch instructions
Another object of the present invention is to provide a branch prediction mechanism in a microprocessor that uses static indicators of a conditional branch instruction to favorably predict its outcome.
In another aspect, it is a feature of the present invention to provide a static branch prediction mechanism for predicting branches in a microprocessor. The static branch prediction mechanism has a static branch predictor, a prediction correlator, and branch history table update logic. The static branch predictor receives branch instructions from an instruction buffer, identifies a biased outcome branch instruction, and provides a static branch prediction for the biased outcome branch instruction. The static branch prediction is based upon observed outcome data corresponding to the biased outcome branch instruction. The static branch predictor also generates a precedence signal to indicate that the static branch prediction takes precedence over a dynamic branch prediction provided by a corresponding branch history table entry. The prediction correlator is coupled to the static branch predictor and a branch history table. The prediction correlator receives the precedence signal and directs the microprocessor to execute a speculative branch in accordance with the static branch prediction or the dynamic branch prediction. The branch history table update logic is coupled to the static branch predictor and the precedence signal. The branch history table update logic updates branch history entries in the branch history table following resolution of the branch instructions, where branch history entries corresponding to resolved biased outcome branch instructions are not updated, and where the precedence signal directs the branch history table update logic to preclude update of the corresponding branch history table entry.
Another advantage of the present invention is that execution speed of an application program is improved because unnecessary pipeline flushes due to incorrect branch predictions are reduced.
A further object of the invention is to provide an apparatus in a microprocessor for predicting branches that eliminates the effects of outcomes of biased outcome conditional branch instructions on historical outcome data associated with unbiased outcome conditional branch instructions.
In a further aspect, it is a feature of the present invention to provide a branch prediction apparatus. The branch prediction apparatus includes a static branch predictor and a prediction correlator. The static branch predictor identifies a biased outcome branch instruction and provides a static branch prediction for the biased outcome branch instruction, where the static branch prediction is based upon observed outcome data corresponding to the biased outcome branch instruction rather than outcomes corresponding to previous executions of the biased outcome branch instruction. The static branch predictor has a static prediction output and a precedence output. The static prediction output indicates whether a first speculative branch to a first target address is to be taken or not taken. The precedence output indicates that the static branch prediction is to take precedence over a dynamic branch prediction, where the dynamic branch prediction is provided by a corresponding entry in a branch history table, and where the precedence output directs branch update logic to preclude update of the corresponding entry following resolution of the biased outcome branch instruction. The prediction correlator is coupled to the static branch predictor and a branch history table. The prediction correlator directs a next instruction pointer to indicate a next sequential instruction address, the first target address, or a second target address.
A further advantage of the present invention is that space in a branch history table is not required for entries pertaining to biased outcome conditional branch instructions.
Yet another object of the present invention is to provide is a method in a microprocessor for mandating that the microprocessor use a static branch prediction over a dynamic prediction and for precluding the outcome of a conditional branch instruction whose static prediction was mandated from influencing outcome data in a branch history table.
In yet another aspect, it is a feature of the present invention to provide a method for performing branch prediction in a microprocessor. The method includes identifying a biased outcome branch instruction; providing a biased static branch prediction for the biased outcome branch instruction, the biased static branch prediction being based upon observed outcome data associated with the branch instruction instead of being based upon outcomes corresponding to previous executions of the biased outcome branch instruction; generating a precedence output to indicate that the biased static branch prediction is to take precedence over a dynamic branch prediction for the biased outcome branch instruction; directing the microprocessor to fetch instructions in accordance with the biased static branch prediction in lieu of the dynamic branch prediction, where the dynamic branch prediction is provided by a corresponding entry in a branch history table; resolving the outcome of the biased outcome branch instruction; and detecting the precedence output and precluding update of the corresponding entry in the branch history table.
Yet another advantage of the present invention is that a method is provided to reduce the confusion created in a branch history table by intermixing outcome results of biased outcome conditional branch instructions with that of unbiased conditional branch instructions.